package com.yaoli.SuanFaDaoLun;

/**
 * Created by YaoLi on 2017/8/13.
 */
public class CutRod {
    public static void main(String[] args) {
        //          1,2,3,4, 5, 6 ,7, 8, 9,10
//        int p [] = {1,5,8,9,10,17,17,20,24,30};
//
//        CutRod cutRod = new CutRod();
//
//        System.out.println(cutRod.calc1(p,30));
//
//        System.out.println();





//        int p [] = {1,5,8,9,10,17,17,20,24,30};
//
//        int r [] = new int[4];
//
//        for(int i = 0 ; i < r.length ; i++){
//            r[i] = Integer.MIN_VALUE;
//        }
//
//        CutRod cutRod = new CutRod();
//
//        System.out.println(cutRod.calc2(p,r,4));
//
//        System.out.println();




        int p [] = {1,5,8,9,10,17,17,20,24,30};

        CutRod cutRod = new CutRod();

        System.out.println(cutRod.calc3(p,4));

        System.out.println();
    }

    /**
     * 常用递归方法
     */
    public int calc1(int p [],int n){
        if(n == 0){
            return 0;
        }
        int max = Integer.MIN_VALUE;
        for(int i = 1 ; i <= n; i++){
            if(i - 1 < p.length){
                max = Math.max(max,p[i - 1] + calc1(p, n - i));
            }
        }
        return max;
    }

    /**
     * 动态规划，带备忘录，自顶向下, top - bottom
     */
    public int calc2(int p [],int r [] , int n){
        if(n == 0){
            return 0;
        }else if(r[n - 1] >= 0){
            return r[n - 1];
        }else{
            int max = Integer.MIN_VALUE;
            for(int i = 1 ; i <= n; i++){
                if(i - 1 < p.length){
                    System.out.println(i+" n - i:"+(n-i));
                    max = Math.max(max,p[i - 1] + calc2(p, r , n - i));
                }
            }
            r[n - 1] = max;
            System.out.println(n+" max:"+max);
            return max;
        }
    }


    public int calc3(int p [] ,int n){
        int r [] = new int[n + 1];
        r[0] = 0 ;

        for(int j = 1 ; j <= n ;j++){

            //子问题求解
            int max = Integer.MIN_VALUE;
            for(int i = 1 ; i <= j ; i++){
                //注意这里是 p[i - 1]，即子问题
                //j - i 表示剩余的空间
                max = Math.max(max,p[i - 1] + r[j - i]);
            }
            r[j] = max;
            //

        }
        return r[ n ];
    }

}
